#include <iostream>
using namespace std;

void countSort(int* a, int n){
    int min = a[0], max = a[0];
    for (int i = 0; i < n; ++i) {
        if (a[i] < min)
            min = a[i];
        if (a[i] > max)
            max = a[i];
    }
    int range = max - min + 1;
    int *countA = (int *) calloc(range,sizeof( int));
    for (int i = 0; i < n; ++i) {
        countA[a[i] - min]++;
    }
    int k = 0;
    for (int i = 0; i < range; ++i) {
        while (countA[i]--)
            a[k++] = i + min;
    }
    free(countA);
}

void printArr(int* a, int n){
    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
    puts("");
}

void testCountSort(){
    int arr[] = {2,4,7,1,3,-4,-2,9,-5,8,4,3,2,6,-2,-5};
    int length = sizeof arr / sizeof( int);
    countSort(arr,length);
    printArr(arr,length);
}

int main() {
    testCountSort();
    return 0;
}
